package william.hash;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ZhangShenao
 * @date 2024/3/7
 * @description <a href="https://leetcode.cn/problems/4sum-ii/">...</a>
 */
public class Leetcode454_四数相加2 {
    /**
     * 借助Map实现
     * 使用一个Map,将nums3和nums4两个数组相加的所有结果保存在Map中,key为加和 value为加和出现的次数
     * 遍历nums1和nums2,将两个数组相加,同时判断Map中是否包含剩余的数,如果包含,则将累加计数
     * <p>
     * 时间复杂度O(N^N) 需要两次双层遍历数组
     * 空间复杂度O(N^N) Map的长度为nums3.length*nums4.length
     */
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        //边界条件校验
        if (nums1 == null || nums1.length < 1 || nums2 == null || nums2.length < 1 || nums3 == null || nums3.length < 1 ||
                nums4 == null || nums4.length < 1) {
            return 0;
        }

        //使用一个Map,将nums3和nums4两个数组相加的所有结果保存在Map中,key为加和 value为加和出现的次数
        Map<Integer, Integer> cache = new HashMap<>();
        for (int i = 0; i < nums3.length; i++) {
            for (int j = 0; j < nums4.length; j++) {
                int sum = nums3[i] + nums4[j];
                int count = cache.getOrDefault(sum, 0);
                cache.put(sum, count + 1);
            }
        }
        int result = 0;
        //遍历nums1和nums2,将两个数组相加,同时判断Map中是否包含剩余的数,如果包含,则将累加计数
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                int minus = -nums1[i] - nums2[j];
                if (cache.containsKey(minus)) {
                    result += cache.get(minus);
                }
            }
        }

        //返回结果
        return result;
    }
}
